package sort;

import java.util.Arrays;
import java.util.Objects;

/**
 * 快速排序
 *
 * @author Ringo
 * @date 2022/3/16 19:21
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 9, 5, 3, 0, 1, 1, 0};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] a) {
        if (Objects.isNull(a) || a.length < 2) return;
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        sort(a, lo, p - 1);
        sort(a, p + 1, hi);
    }

    // 快排找到分割点
    private static int partition(int[] a, int lo, int hi) {
        int left = lo, right = hi;
        int v = a[lo];
        while (left < right) {
            while (left < right && a[right] > v) right--;
            if (left < right) a[left++] = a[right];
            while (left < right && a[left] <= v) left++;
            if (left < right) a[right--] = a[left];
        }
        a[left] = v;
        return left;
    }
}
